/*
 * @lc app=leetcode.cn id=142 lang=javascript
 *
 * [142] 环形链表 II
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
// 快慢指针

// var detectCycle = function(head) {
//   if(!head) return null;
//   let pre = head, cur = head; 
//   let flg = head;
//   while(cur && cur.next) {
//     pre = pre.next;
//     cur = cur.next.next;
//     if(pre === cur){
//       while(cur !== flg) {
//         cur = cur.next;
//         flg = flg.next;
//       }
//       return cur;
//     }
//   }
//   return null;
// };

/**
 * 复习 2021-08-04
 */
// var detectCycle = function(head) {
//   if(!head) return null;
//   let pre = head, tail = head;
//   while(tail && tail.next) {
//     pre = pre.next;
//     tail = tail.next.next;
//     if(pre === tail) {
//       let pre = head;
//       while(pre != tail) {
//         tail = tail.next;
//         pre = pre.next;
//       }
//       return tail; 
//     };
//   }
//   return null;
// }

// 一起学算法
var detectCycle = function(head) {
  if(!head || !head.next) return null;
  
  let p = head.next, q = head.next.next;
  // 判断是否有环
  while(p != q && q && q.next) {
    p = p.next;
    q = q.next.next;
  }
  if(p != q) return null;

  p = head;
  while(p != q) {
    p = p.next;
    q = q.next;
  }
  return p;
}

// @lc code=end

